package com.zhupf.binarySearch;

/**
 * @author zhupf
 * @date 2024年01月12日 10:09
 * @Description
 *
 * 35. 搜索插入位置
 */
public class SearchInsert {

    public static void main(String[] args) {
        int[] nums = {1,3,5,6};
        searchInsert(nums,2);
    }

    public static int searchInsert(int[] nums, int target) {
        if(nums[0]> target){
            return 0;
        }
        if(nums[nums.length-1] < target){
            return nums.length;
        }
        int mid;
        int start = 0;
        int end = nums.length-1;
        while (start<end){
            mid = start+(end-start)/2;
            if(nums[mid] == target){
                return mid;
            }
            if(start == end){
                return start;
            }
            if((end-start) == 1){
                return nums[start] == target?start:start+1;
            }
            if(nums[mid]>target){
                end = mid;
            }
            if(nums[mid]<target){
                start = mid;
            }
        }
        return 0;
    }

    public static int searchInsert2(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        int mid;
        int ans = 0;
        while (left <= right){
            mid = left +(right-left)/2;
            if(nums[mid]>=target){
                ans = mid;
                right = mid -1;
            }else {
                ans = mid;
                left = mid +1;
            }
        }
        return ans;
    }
}
